/**
 * 给定源数组与目标数组，对源数组每次操作：
 * 1. 选一个子数组
 * 2. 将该子数组插回去
 * 
 * 问将源数组变为目标数组的最少步数
 * 由于数组长度只有6，使用广搜即可
 */
class Solution {
using vi = vector<int>;
vi W, Src, Dst;
int SrcCode, DstCode;
vi Flag;
int N;
public:
    int minSplitMerge(vector<int>& nums1, vector<int>& nums2) {
        N = nums1.size();
        W.assign(nums1.begin(), nums1.end());
        sort(W.begin(), W.end());    
        Src.clear(); Dst.clear();
        for(auto i : nums1){
            Src.emplace_back(lower_bound(W.begin(), W.end(), i) - W.begin());
        }
        for(auto i : nums2){
            Dst.emplace_back(lower_bound(W.begin(), W.end(), i) - W.begin());
        }

        SrcCode = this->encode(Src);
        DstCode = this->encode(Dst);
        if(SrcCode == DstCode) return 0;

        Flag.assign(600000, 0);
        queue<int> q;
        q.push(SrcCode);
        Flag[SrcCode] = 1;

        decltype(q.size()) sz = 0;
        int step = 0;
        while(sz = q.size()){
            ++step;
            while(sz--){
                auto h = q.front(); q.pop();
                
                vi vec;
                this->decode(h, vec);

                for(int i=0;i<N;++i)for(int j=i;j<N;++j){
                    if(0 == i and N - 1 == j) continue;

                    // 将i,j取出
                    vi tmp(vec.begin() + i, vec.begin() + j + 1);
                    vi src(vec.begin(), vec.end());
                    src.erase(src.begin() + i, src.begin() + j + 1);

                    // 将tmp依次插入到src的每一个位置
                    for(int k=0;k<=src.size();++k){
                        vi tt(src.begin(), src.end());
                        tt.insert(tt.begin() + k, tmp.begin(), tmp.end());
                        auto ttCode = this->encode(tt);
                        if(ttCode == DstCode) return step;
                        if(0 == Flag[ttCode]){
                            Flag[ttCode] = 1;
                            q.push(ttCode);                            
                        }

                    }
                }
            }
        }
        return -1;
    }

    int encode(const vi & v){
        int ans = 0;
        for(auto i : v) ans = ans * 10 + i;
        return ans;
    }

    void decode(int code, vi & vec){
        while(code){
            vec.emplace_back(code % 10);
            code /= 10;
        }
        while(vec.size() < N) vec.emplace_back(0);
        reverse(vec.begin(), vec.end());
    }
};